package daily.year2024.m10;

/**
 * 188.买卖股票的最佳时机IV
 *
 * @author wjs 2024/10/29
 */
public class d29 {
    class Solution1 {
        public int maxProfit(int k, int[] prices) {
            int[][] dp = new int[k][2];
            for(int i=0;i < k;i++) {
                dp[i][1] = -prices[0];
            }
            for(int i=1;i < prices.length;i++) {
                dp[0][1] = Math.max(dp[0][1],-prices[i]);
                dp[0][0] = Math.max(dp[0][0],dp[0][1]+prices[i]);
                for(int j=1;j < k;j++) {
                    dp[j][1] = Math.max(dp[j][1],dp[j-1][0]-prices[i]);
                    dp[j][0] = Math.max(dp[j][0],dp[j][1]+prices[i]);
                }
            }
            return dp[k-1][0];
        }
    }
}
